package Study;

import org.junit.Test;

import java.util.*;

/**
 * @author:MJS
 * @create: 2023-03-28-16:16
 * @description:
 */
public class Knowledge3 {

    long pre = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        //如果节点是空的话  也符合二叉树
        if (root == null) return true;
        //先校验左子树
        boolean leftBoolean = isValidBST(root.left);
        //判断当前节点跟上一个节点的值
        if (root.val <= pre) return false;
        pre = root.val;
        //校验右子树
        boolean rightBoolean = isValidBST(root.right);
        return leftBoolean && rightBoolean;
    }

    //给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。
    public void recoverTree(TreeNode root) {
        if (root == null) return;
        List<TreeNode> res = new ArrayList<>();
        dfs(root, res);
        int len = res.size();
        TreeNode x = null;
        TreeNode y = null;
        for (int i = 0; i < len - 1; i++) {
            if (res.get(i).val > res.get(i + 1).val) {
                y = res.get(i + 1);
                if (x == null) {
                    x = res.get(i);
                }
            }
        }
        if (x != null && y != null) {
            int tem = x.val;
            x.val = y.val;
            y.val = tem;
        }
    }

    //中序遍历
    private void dfs(TreeNode root, List<TreeNode> res) {
        if (root == null) return;
        dfs(root.left, res);
        res.add(root);
        dfs(root.right, res);
    }

    //是否是相同的二叉树
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        if (p.val != q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        //调用递归函数，比较左节点和右节点
        return dfsIsSymmetric(root.left, root.right);
    }

    private boolean dfsIsSymmetric(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        if (left.val != right.val) return false;
        return dfsIsSymmetric(left.left, right.right) && dfsIsSymmetric(left.right, right.left);
    }

    //前序遍历
    public List<Integer> traversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        NLR(res, root);
        return res;
    }

    private void NLR(List<Integer> res, TreeNode root) {
        if (root == null) return;
        res.add(root.val);
        NLR(res, root.left);
        NLR(res, root.right);
    }

    private void LNR(List<Integer> res, TreeNode root) {
        if (root == null) return;
        LNR(res, root.left);
        res.add(root.val);
        LNR(res, root.right);
    }

    private void LRN(List<Integer> res, TreeNode root) {
        if (root == null) return;
        LRN(res, root.left);
        LRN(res, root.right);
        res.add(root.val);
    }

    //前序遍历
    public List<Integer> traversalNLR(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        if (root == null) return res;
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                res.add(root.val);
                stack.push(root.left);
                root = root.left;
            }
            TreeNode tmp = stack.pop();
            root = tmp.right;
        }
        return res;
    }

    //中序遍历
    public List<Integer> traversalLNR(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        if (root == null) return res;
        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                TreeNode tmp = stack.pop();
                res.add(tmp.val);
                root = tmp.right;
            }
        }
        return res;
    }

    //后序遍历
    public List<Integer> traversalLRN(TreeNode root) {
        LinkedList<Integer> res = new LinkedList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        if (root == null) return res;
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                res.addFirst(root.val);
                stack.push(root);
                root = root.right;
            }
            TreeNode tmp = stack.pop();
            root = tmp.left;
        }
        return res;
    }

    public List<TreeNode> generateTrees(int n) {
        ArrayList<TreeNode>[] dp = new ArrayList[n + 1];
        dp[0] = new ArrayList<>();
        if(n == 0) return dp[0];
        dp[0].add(null);
        //长度从1到n
        for (int len = 1; len <= n; len++) {
            dp[len] = new ArrayList<TreeNode>();
            //将不同的数字作为根节点
            for (int root = 1; root <= len; root++) {
                //左子树的长度
                int left = root - 1;
                //右子树的长度
                int right = len - root;
                for (TreeNode leftTree : dp[left]) {
                    for (TreeNode rightTree : dp[right]) {
                        TreeNode treeNode = new TreeNode(root);
                        treeNode.left = leftTree;
                        treeNode.right = clone(rightTree,root);
                        dp[len].add(treeNode);
                    }
                }
            }
        }
        return dp[n];
    }

    private TreeNode clone(TreeNode n, int offset) {
        if (n == null) return null;
        TreeNode treeNode = new TreeNode(n.val + offset);
        treeNode.left = clone(n.left, offset);
        treeNode.right = clone(n.right, offset);
        return treeNode;
    }
    //DFS 深度
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        int leftCount = maxDepth(root.left);
        int rightCount = maxDepth(root.right);
        return Math.max(leftCount,rightCount)+1;
    }

    private Map<Integer,Integer> indexMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int len = preorder.length;
        //构造哈希映射，以空间换时间 快速定位根节点
        //根据前序 可以定位到 根节点，方便去找到中序 上的根节点的位置
        indexMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < len; i++) {
            indexMap.put(inorder[i],i);
        }
        return buildTreePre(preorder,inorder,0,len-1,0,len-1);
    }

    private TreeNode buildTreePre(int[] preorder, int[] inorder, int preLeft, int preRight, int inLeft, int inRight) {
        if(preLeft > preRight  || inLeft > inRight) return null;
        //前序遍历中的第一个节点即根节点
        int preRoot = preorder[preLeft];
        //先把根节点建立出来
        TreeNode root = new TreeNode(preRoot);
        //从中序遍历中定位根节点
        Integer inRoot = indexMap.get(preRoot);
        //得到左子树的节点数目
        int sizeLeft = inRoot - inLeft;
        //递归构造左子树 并连接到根节点
        //先序遍历中 【左边界+1开始的sizeLeft】个元素就对应了中序遍历中【左边界开始到根节点位-1】的元素
        root.left = buildTreePre(preorder,inorder,preLeft+1,preLeft+sizeLeft,inLeft,inRoot-1);
        //递归构造右子树，并连接到根节点
        //先序遍历中的【左边界+1+左子树节点数目 开始到 右边界】的元素对应【根节点定位+1 到右边界】的元素
        root.right = buildTreePre(preorder,inorder,preLeft+1+sizeLeft,preRight,inRoot+1,inRight);
        return root;
    }

    @Test
    public void test33(){
        int[] inorder = {3,2,1};
        int[] postorder = {3,2,1};
        TreeNode treeNode = buildTreeP(inorder, postorder);
        System.out.println(treeNode);
    }

    public TreeNode buildTreeP(int[] inorder, int[] postorder) {
        int len = postorder.length;
        indexMap = new HashMap<>();
        for (int i = 0; i < len; i++) {
            indexMap.put(inorder[i],i);
        }
        return buildTreePost(inorder,postorder,0,len - 1,0,len -1);
    }

    private TreeNode buildTreePost(int[] inorder, int[] postorder, int inLeft, int inRight, int postLeft, int postRight) {
        if(inLeft > inRight || postLeft > postRight) return null;
        //通过后序数组找到根节点的值
        int postRootValue = postorder[postRight];
        //创建树
        TreeNode treeNode = new TreeNode(postRootValue);
        //通过根节点的值查询中序遍历中的根节点的位置
        Integer inRoot = indexMap.get(postRootValue);
        //右子树的长度
        int sizeRight = inRight - inRoot;
        //递归左子树
        //中序遍历
        treeNode.left = buildTreePost(inorder,postorder,inLeft,inRoot - 1,postLeft,postRight - sizeRight - 1);
        //递归右子树
        //中序遍历
        treeNode.right = buildTreePost(inorder,postorder,inRoot +1,inRight,postRight - sizeRight,postRight - 1);
        return treeNode;
    }


    public TreeNode sortedListToBST(ListNode head) {

        List<Integer> list = new ArrayList<>();
        while (head != null){
            list.add(head.val);
            head = head.next;
        }
        return helper(list,0,list.size() - 1);
    }

    private TreeNode helper(List<Integer> list, int start, int end) {
        //终止条件
        if(start > end){
            return null;
        }
        //获取到中间的值
        int mid = (start + end) / 2;
        //创建树
        TreeNode treeNode = new TreeNode(list.get(mid));
        treeNode.left = helper(list,start,mid - 1);
        treeNode.right = helper(list,mid + 1,end);
        return treeNode;
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        int len = nums.length;
        return helper(nums,0,len -1);
    }

    private TreeNode helper(int [] nums, int start ,int end){
        //终止条件
        if(start > end ) return null;
        //找到中间的位置  如果是奇数的话 只有一个值，如果是偶数的话 选择靠前的那个值
        int mid = (start + end) / 2;
        //创建树
        TreeNode treeNode = new TreeNode(nums[mid]);
        //左子树
        treeNode.left = helper(nums,start,mid -1);
        //右子树
        treeNode.right = helper(nums,mid + 1,end);
        return treeNode;
    }

    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }else{
            return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
    }

    private int height(TreeNode root){
        if(root == null){
            return 0;
        }else{
            return Math.max(height(root.left),height(root.right)) + 1;
        }
    }

    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null)return false;
        if(root.left == null && root.right == null){
            return targetSum == root.val;
        }
        return hasPathSum(root.left,targetSum - root.val) || hasPathSum(root.right,targetSum - root.val);
    }

    List<List<Integer>> res = new LinkedList<>();
    Deque<Integer> path = new LinkedList<Integer>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root,targetSum);
        return res;
    }

    private void dfs(TreeNode root, int targetSum) {
        if(root == null) return;
        path.offerLast(root.val);
        targetSum -= root.val;
        if(root.left == null && root.right == null && targetSum == 0){
            res.add(new LinkedList<>(path));
        }
        dfs(root.left,targetSum);
        dfs(root.right,targetSum);
        path.pollLast();
    }


}
